Computer-aided techniques are known to include Computer-Aided Geometric Design or CAGD, which relates to software solutions for representing objects in forms suitable for computer computations in CAD and CAM systems. Computer-aided design (or CAD) relates to software solutions for authoring product design. Similarly, CAE is an acronym for Computer-Aided Engineering, e.g. it relates to software solutions for simulating the physical behavior of a future product. CAM stands for Computer-Aided Manufacturing and typically includes software solutions for defining manufacturing processes and operations.
A number of systems and programs are offered on the market for the design of parts, assemblies of parts and products thereof, such as the one provided by Dassault Systemes under the trademark CATIA (Computer Aided Three Dimensional Interactive Application). CATIA is a multi-platform CAGD/CAD/CAM/CAE software suite, commonly referred to as a 3D Product Lifecycle Management (PLM) software suite. It supports multiple stages of product development (CAx), ranging from conceptualization of objects shapes (CAGD), through design (CAD) and manufacturing (CAM), until analysis (CAE). This software suite is customizable via application programming interfaces (API). Some versions can be adapted in various programming languages, under dedicated APIs.
These so-called CAGD/CAD systems notably allow a user to construct and manipulate complex three dimensional (3D) models of objects or assemblies of objects. CAD systems thus provide a representation of modeled objects using edges or lines, in certain cases with faces. These CAD systems manage parts or assemblies of parts as modeled objects, which are mainly specifications of geometry. In particular, CAD files contain specifications, from which geometry is generated. From geometry, a representation is generated. Specifications, geometry and representation may be stored in a single CAD file or multiple ones. CAD systems include graphic tools for representing the modeled objects to the designers; these tools are dedicated to the display of complex objects—the typical size of a file representing an object in a CAD system extending up to the range of a Mega-byte for part, and an assembly may comprise thousands of parts. A CAD system manages models of objects, which are stored in electronic files.
Designing a mechanical part with a known CAGD/CAD system can be seen as defining the geometrical shape and dimensions of said part so as to fit functional and manufacturing requirements. Mainly, the resulting shape is a combination of basic features such as pad, pocket, groove, shaft etc. created by the designer. Through complex geometrical and topological computations, the CAGD/CAD system yields the boundary representation of the solid (mechanical part) as e.g. a closed and oriented surface.
One knows the concept of swept volumes, e.g. in the field of geometric design (CAGD), machining simulation, robotics, or digital mockup. Given a solid, called “profile” in the following, and a trajectory thereof, we call the swept volume the union of all positions of the profile along the said trajectory. The representation of swept volumes can be used to design shapes, simulate the process of material removal or addition, detect collisions and compute clearance in moving parts and mechanisms. For instance the calculation of a swept volume is useful to determine the required space of a vehicle motor that is vibrating during its functioning. Also, the calculation of a swept volume is useful to determine the required space of a wheel of a vehicle while said wheel turns left and right and moves up and down thanks to shock absorbers. Also, the swept volume is useful to determine the required space of a manufacturing tool.
Computation of so-called swept volumes has been presented in the European Patent Application No. 08291047.2 of Nov. 7, 2008.
Polyhedral modeling and processing is ubiquitous in the context of CAGD. Indeed performing robust and accurate Boolean operations (e.g. union, intersection, subtraction) on polyhedral solids is an essential requirement in this context. Industrial implementation of such operators makes use of floating point representations or integer representations of coordinates together with so called epsilon-programming heuristics.
Roughly speaking, epsilon-programming is to replace equality tests x=y by “up to epsilon” equality tests |x−y|≦ε, where ε is the traditional numerical threshold notation. Details can be found in “Robustness and Randomness”, D. Michelucci, J. M. Moreau, S. Foufou—Lecture Notes In Computer Science, 2008, Springer.
From a theoretical point of view, usual geometric modeling and processing based on the floating point paradigm lack rigorous and scientific foundation. In practice, developing a robust Boolean operator based on floating point framework is difficult, costly and is more an art than a science. Indeed, the floating point rounding errors may induce combinatorial inconsistencies, e.g. topological inconsistencies.
The epsilon-programming paradigm allows overcoming these inconsistencies but, the techniques based on the epsilon-programming are not supported by a sound theoretical framework: indeed, they require case by case expertises which make the achievement of complete robustness a never ending task.
Alternatively recent implementations use the exact computation paradigm based on the exact predicates technology, as detailed in “Robustness in geometric computations”, C. M. Hoffmann, Journal of Computing and Information Science in Engineering, 1:143, 2001, “Robust geometric computation”, C. K. Yap, Handbook of discrete and computational geometry, pages 653-668, 1997, and “Efficient Delaunay triangulation using rational arithmetic”, M. Karasick, D. Lieber, and L. R. Nackman, ACM Transactions on Graphics (TOG), 10(1):71-91, 1991.
In the exact computation paradigm, when some geometry has to be constructed, one has to use rational or algebraic numbers representations in the result which leads to time and space consuming algorithms. As, in real life CAGD applications, the input of a geometric processing algorithm is generally the output of a previous one, a pure exact computation approach is not possible since it would produce an exponential growth of the number representations.
It is therefore necessary to “round” the coordinates of the output from rational to floating point numbers. Unfortunately, such a rounding procedure is not safe in general. Indeed, this rounding may create local self-intersections, as illustrated on FIG. 1. The polygon 4 is a valid one because there is no self-intersection. The background grid represents the rounded numerical values. Rounding is to replace each vertex of the initial polygon by its closest point of the grid. The dotted polygon 2 is the rounding result of the black polygon, and this polygon 2 is invalid because of a self intersection 3.
Such a self-intersection invalidates the result because no self intersection is allowed. Moreover, a self-intersection is likely to make further algorithms fail.
The natural relationship between conventional polyhedral representations of solids with polyhedral chains have been highlighted in the two following papers: “Convex polyhedral chains: a representation for geometric data”, O. Gunther and E. Wong, Computer Aided design, volume 21 number 3 April 1989 and “Geometric modelling Based on simplicial chains”, F. R. Feito and M. Rivero, Comput. & Graphics, Vol. 22, No. 5, pp. 611-619, 1998.
In the first paper, the authors suggest to represent the solid through a kind of CSG (constructive solid geometry). The chains are expressed as linear combinations of polytopes, each polytope being represented by its associated finite family of half-spaces. Implementing modeling operators such as Boolean operations on this representation does not require the construction of any explicit vertex, since the robustness of the approach consists precisely on avoiding vertex based representations.
The second paper shows simple relationships between Boolean operators and algebraic operations on the corresponding chains and in particular on a representation called “normal chain”, where a chain is expressed as linear combinations of oriented simplices sharing all the origin as one of their vertices. For example, the intersection of two solids, represented by chains formal sum of respectively n and m tetrahedra, consists in a formal sum of n*m triangulation of the intersection of the corresponding n*m pairs of tetrahedra.
Both papers highlight the natural relationship between conventional polyhedral representations of solids with polyhedral chains. However, these papers rely on Boolean operations which are not generalized Boolean operators.
In fact, all CAGD systems implement Boolean operations through the same structure. Details of the algorithm may change from a CAGD system to another, but the main steps are the same. The inputs of the Boolean operation are two solids A and B defined by their valid boundary representation. Valid boundary representation means that the boundary of the solid is a closed surface with no self-intersection. Standard Boolean operations are union, intersection and subtraction, which are in general noted ∪, ∩ and −.
Traditional algorithms strongly rely on the hypothesis that the input solids are valid, and provides a valid solid. In other words, the boundary solids A and B do not have any self intersection. The steps of a tradition algorithm are the following, in relations with FIGS. 2-7:
1. Input two solids A and B defined by their valid boundary representation (FIG. 2);
2. Trim the boundary of solid A with the boundary of solid B, and inversely (FIG. 3).
3. Position each portion of the boundary of solid A with respect to solid B. Portions of boundary of solid A are inside or outside solid B (FIG. 4).
4. Position each portion of the boundary of solid B with respect to solid A. Portions of boundary of solid B are inside or outside solid A (FIG. 5).
5. Depending on the Boolean operation type, discard the useless portions of boundary:                (i) Union A+B: discard portions of boundary of solid A inside solid B and portions of boundary of solid B inside solid A.        (ii) Intersection A·B: discard portions of boundary of solid A outside solid B and portions of boundary of solid B outside solid A.        (iii) Subtraction A−B: discard portions of boundary of solid A inside solid B and portions of boundary of solid B outside solid A (FIG. 6).        
6. Synthesize the resulting solid by merging the portions of boundary provided by previous step (FIG. 7).
To summarize the above analysis, the prior art shows too much sensitivity with respect to rounding errors because usual polyhedral representations depend on numerical values. Indeed, a state of the art polyhedron may produce self-intersections, thus making the result inconsistent according to the state of the art validity criterion. Consequently, there is a lack of robustness of the solutions of the prior art as their validity may be affected.